The present invention relates to a field of a computer application apparatus, especially an image processor and an image processing apparatus using it.
Furthermore, more in detail, the present invention is related with template matching to extract a region resembling a template image from an object image, and with moving-average filtering for an image data of each pixel, which are executed by using pixels in a rectangular filtering region including the pixel, in an object image, the size of the rectangular region being preset.
The present invention relates to a pattern recognition method and an apparatus using the method which are used for positioning elements in a semiconductor apparatus, searching parts in a FA line, a remote sensing, and so forth.
In various fields using an image processing, a template matching method is used to search a partial area in an image (referred to as a search image) obtained by a sensor, which resembles a specified image pattern (referred to as a template). Such a template matching method is disclosed, for example, in "Image Analysis Handbook", by Mikio Takagi and Akihisa Shimoda, University of Tokyo Press (1991). In a template matching method, it is often performed that each pixel is represented by a n-bit data for expressing a multilevel gradation image data, and a normalized correlation coefficient is used as a measure for a similarity of patterns. A normalized correlation coefficient r(i, j) is expressed by the following equation in which t(m, n) (m=0, 1, . . . , M-1; n=0, 1, . . . , N-1) is a data value of a pixel in a template, s(i+m, j+n) (m=0, 1, . . . , M-1; n=0, 1, . . . , N-1); and (i, j) is a starting point of a sub-image) is the sub-image in a search image, of which a similarity to the template is to be evaluated, and P is the number of pixels in the template. ##EQU1##
In performing template matching, the above-described normalized correlation coefficient is obtained for each of a plurality of sub-images, and one or plural sub-images which are determined to resemble a template are selected in accordance with the obtained normalized correlation coefficients. A method using a normalized correlation coefficient can perform template matching without receiving effects of variations between image data values of pixels in a template image and those of pixels in a search image, the variation being caused, for example, by changes in lighting.
Since calculation steps or data amount to be calculated are very huge in a pattern matching method using the above-mentioned normalized correlation coefficient, a method for efficiently obtaining a normalized correlation coefficient has been investigated.
In one of existing methods for performing a template matching method at a high speed, absolute values of differences between image data values of pixels in a template image and those of pixels in a sub-image to be processed, of a search image, are accumulated while a normalized correlation coefficient is obtained for the sub-image, and the process for calculating the normalized correlation coefficient is closed, if a sum of the accumulated absolute values exceeds a preset threshold value.
In the above-mentioned existing measure, since the accumulated sum of absolute values of differences between image data values of pixels in a template image and those of pixels in a sub-image to be processed is used to close a process for obtaining a normalized correlation coefficient, there exists a problem in which if variations of image data values of pixels in a template image and those of pixels in a sub-image of a search image are caused, for example, by changes in lighting, a process for obtaining a normalized correlation coefficient is wrongly closed for even a sub-image which has a high similarity to the template image because of the large accumulated sum of absolute value of the differences. In the following, this problem will be explained in detail with reference to FIG. 13 and FIG. 14.
FIG. 13 is an example of a template image, and FIG. 14 is an example of a search image for which a sub-image resembling the template image is searched. In these figures, squares shows pixels, and values shown in the squares indicate levels in gradation of images. The similarity between two images is to be determined, not based on the nearness between absolute image data values of pixels in the two images, but on the nearness between relative local changing tendencies in image data values of pixels in the two images. Therefore, a sub-image, in the search image shown in FIG. 14, most resembling the template image shown in FIG. 13, is a sub-image shown at the right-upper part in FIG. 14, which are composed of pixels 1403, 1404, 1405, 1408, 1409, 1410, 1413, 1414 and 1415. In fact, a normalized correlation coefficient between the template image and the sub-image is 1.0. However, the value in a accumulated sum of absolute values of difference between image data values, which is used to close a process for obtaining a normalized correlation coefficient in the existing methods, is 360 for the sub-image at the right-upper part, and is much larger than 80 for a sub-image at the left-lower part, which is composed of pixels 1411, 1412, 1413, 1416, 1417, 1418, 1421, 1422 and 1423. Therefore, if a threshold value of the accumulated sum, which is set to close a process for obtaining a normalized correlation coefficient, is preset to a value in a range 80 to 460, the sub-image at the left-lower part is searched, but searching the sub-image at the right-upper part is closed in the midst. Hereupon, the sub-image at the left-lower part is an image of a laterally striped pattern.
Furthermore, in many cases including the above example, it is difficult to set an adequate threshold value for the above-mentioned accumulated sum.
Furthermore, an image processing technique is indispensable to fields using a microscope, medical equipment, etc., and also to a remote sensing technique, an inspection technique of a product, etc. In image processing, a filtering method to remove noise components, or to improve the quality of a processed image takes an important role, and various algorithms for implementing filtering methods have been devised, and some of them have been incorporated into hardware systems.
A moving-average filtering method used as one of filtering methods performs filtering for an image data of each object pixel in an image to be processed, by averaging image data values of pixels in a rectangular region including the object pixel, the size of the rectangular (kernel size) being usually preset. In the following, outline of a moving-average filtering method will be explained with reference to FIGS. 35A and 35B. Hereupon, FIG. 35A is an image composed of 9 pixels in the column direction (the lateral direction).times.8 pixels in the row direction. Numerals 211 -289 indicate pixels. FIG. 35B shows an image obtained by executing moving-average filtering with a kernel size of 5 pixels.times.5 pixels, for image data of pixels shown in FIG. 35A. Numerals 211'-289' indicated pixels of which image data values were filtered. For example, an image data value of a pixel 233' is an average value of image data values of pixels in a region for 5 pixels in the row direction and 5 pixels in the column direction, in which the pixel 233 is centered, that is, an average value of image data values of pixels 211, 212, 213, 214, 215, 221, 222, 223, 224, 225, 231, 232, 233, 234, 235, 241, 242, 243, 244, 245, 251, 252, 253, 254 and 255. Similarly, an image data value of a pixel 234' is an average value of image data values of pixels in a region for 5 pixels.times.5 pixels, in which the pixel 234 is centered, further an image data value of a pixel 235' is an average value of image data values of pixels in a region for 5 pixels .times.5 pixels, in which the pixel 235 is centered, and so on. Thus, an image data value of each pixel in the image shown in FIG. 35B has an average value of image data values of pixels in a region having the kernel size for 5 pixels.times.5 pixels, in which the corresponding pixel in the image shown in FIG. 35A is centered.
An efficient average-moving filtering method has been devised in Japanese Patent Laid-Open 51257/1995. FIG. 36 shows a schematic block diagram of a system for implementing the devised average-moving filtering method of JP-A-51257/1995. The system shown in FIG. 36 is composed of an image input device 3601 for inputting an image, an image memory 3604 for storing image data of an input image, a calculation circuit 3602 for calculating an average value of image data values of n pixels in the row direction, a memory 3603 for storing calculated average values for pixels in the row direction, and a calculation circuit 3605 for obtaining a moving-average value by using the average values stored in the memory 3603.
Image data of an image input by the image input device 3601 are stored in the image memory 3604, and the calculation circuit 3602 obtains an average value of image data of n pixels in the row direction, in parallel to storing of the image data. In the following, procedures to obtain a moving-average value by using data stored in the memory 3603 will be explained with reference to FIG. 37. In FIG. 37, numeral 2101 indicates a region for 5 pixels.times.5 pixels, which is to be presently processed for obtaining an moving-average value, and numeral 2102 indicates a region (referred to as kernel region) for 5 pixels.times.5 pixels, which was previously processed to obtain an moving-average value. Moreover, numerals 2103 and 2104 indicate two areas, each of the areas being composed of n (=5) pixels in the row direction, respectively. A position of a pixel centered in an kernel region changes from the most left position to the most right position in the top row, in the image shown in FIG. 37, and the position of a center pixel similarly changes in the successive rows, and so forth. An moving-average value for the region 2101 is obtained based on the following relation: a moving-average value for the region 2101=a moving-average value for the region 2102-(an average value for the area 2103-an average value for the area 2104)/(the number of lines in the region 2101).
The average values for the areas 2103 and 2104 shown in FIG. 37 are stored in the memory 3603 shown in FIG. 36, and since the moving-average value for the region 2102 was obtained in the previous calculation step, the value is held in the calculation circuit 3605. Therefore, the moving-average value for the region 2101 can be obtained by reading the average values for the areas 2103 and 2104 out of the memory 3603 and using them.
In the above-mentioned conventional technique, when average values for every five pixels in the row direction are written in the memory 3603, access of the memory 3603 can be performed by designating successive addresses in the column direction. However, when the average values for the areas 2103 and 2104 are read out of the memory 3603 to obtain the moving-average value for the area 2101, it is necessary to perform access to the memory 3603 by designating discontinuous addresses.
Generally, a high frequency cycle mode, for example, a high speed page mode, is provided for a memory such as a DRAM, a synchronous DRAM, etc., and it is possible to perform access to such a memory for successive addresses at a high speed.
Therefore, if a DRAM or a synchronous DRAM is used for the memory 3603, although since it is possible to perform access to the memory 3603 by designating successive addresses in the row direction, high-speed access to the memory 3603 can be performed during a data write-in mode, high-speed access to the memory 3603 is difficult during a data read-out mode, since access to the memory 3203 is performed by designating discontinue addresses.